package algorithmTopics.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 树节点
 *
 * @author 86155
 * @date 2025/04/26
 * 用于树算法的练习
 */
public class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }


    public void add() {

    }
    //把升序的数组转化为，平衡的二叉搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return  null;
        }
        return toBSTHelper(nums,0,nums.length-1);
    }
    private TreeNode toBSTHelper(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        int middle = (start+end) >>> 1;
        TreeNode treeNode = new TreeNode(nums[middle]);
        treeNode.left= toBSTHelper(nums, start, middle - 1);
        treeNode.right= toBSTHelper(nums, middle+ 1, end);
        return treeNode;
    }

    //二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> res = new ArrayList<>();
        oneLevelOrder(root,0, res);
        return res;
    }
    /**
     * 逐层打印
     *
     * @param root     根
     * @param onePiece 当前的节点
     * @param res      res 结果集合
     */
    public void oneLevelOrder(TreeNode root, Integer onePiece , List<List<Integer>> res ) {
        if (root == null) {
            return;
        }
        //要先把下一层初始化
        if (onePiece >= res.size()) {
            res.add(new ArrayList<>());
        }
        res.get(onePiece).add(root.val);

        oneLevelOrder(root.left, onePiece +1, res);

        oneLevelOrder(root.right , onePiece +1 ,res);

    }

    // 判断是不是对称二叉树
    public boolean isSymmetric(TreeNode root) {
        // 同时取 两个子树的节点的值 同时比较
        if (root.left == null && root.right == null) {
            // 表示没有值
            return true;
        }
        if (root.left != null && root.right != null) {
            if (isSymmetric(root.left, root.right) == 101) {
                return true;
            } else {
                return false;
            }
        }
        return false;

    }

    public int isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return 101;
        }
        int a = 1000;
        int b = 1000;
        if (left != null) {
            a = left.val;
        }
        if (right != null) {
            b = right.val;
        }
        if (a != b) {
            return -101;
        }

        if (isSymmetric(left.left, right.right) == -101) {
                return -101;
        }

        if (isSymmetric(left.right, right.left) == -101) {
                return -101;
        }

        //101 表示是对称
        return 101;
    }


    public int maxDepth(TreeNode root) {
        //空 树
        if (root == null) {
            return 0;
        }
        int res = 1;
        if (root.left == null && root.right == null) {
            return res;
        }
        // 有分叉就记录一下当前的层数
        if (root.right != null && root.left != null) {
            int i = maxDepth(root.left);
            int j = maxDepth(root.right);
            res += (i>j?i:j);
        } else if (root.left != null) {
            int i = maxDepth(root.left);
            res += i;
        } else {
            int i = maxDepth(root.right);
            res += i;
        }

        return res;
    }
    //方法二 输出树的层数
//    public int maxDepth(TreeNode root) {
//        return root==null? 0 : Math.max(maxDepth(root.left), maxDepth(root.right))+1;
//    }


    //判断是不是搜索二叉树
    private TreeNode pre;
    public boolean isValidBST(TreeNode root) {
        //中序遍历是从小到大的顺序输出的 ，判断是不是从小到大就行
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }
        //如果当前节点小于中序遍历前一个节点
        if (pre != null && pre.val >= root.val) {
            return false;
        }
        pre = root;
        if (!isValidBST(root.right)) {
            return false;
        }

        //默认是搜索二叉树
       return true;

    }
    public ArrayList<Integer> middleOrder(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        if (root.left != null) {
            ArrayList<Integer> integers = middleOrder(root.left);
            integers.forEach(integer -> res.add(integer));
        }
        res.add(root.val);
        if (root.right!= null) {
            ArrayList<Integer> integers = middleOrder(root.right);
            integers.forEach(integer -> res.add(integer));
        }
        return res;
    }

    //中序遍历，输出数组
//    public ArrayList<Integer> middleOrder(TreeNode root) {
//        ArrayList<Integer> res = new ArrayList<>();
//        if (root == null) {
//            return res;
//        }
//
//        //有子节点
//        if (root.left != null && root.right!=null) {
//            ArrayList<Integer> l = middleOrder(root.left);
//            ArrayList<Integer> r = middleOrder(root.right);
//            l.add(root.val);
//            r.forEach(integer -> {
//                l.add(integer);
//            });
//            return l;
//
//        } else if (root.right != null) {
//            ArrayList<Integer> r = middleOrder(root.right);
//            r.add(0,root.val);
//            return r;
//        } else if (root.left != null) {
//            ArrayList<Integer> l = middleOrder(root.left);
//            l.add(root.val);
//            return l;
//        }
//        res.add(root.val);
//        return res;
//    }

}
